#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/13 14:10
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _22_generateParenthesis.py
from copy import deepcopy


class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []

        def dfs(path, o, c):
            if o>n or c>o: #剪枝
                return
            if len(path) == n*2:
                res.append(deepcopy(path))
                return

            dfs(path+"(", o+1, c)
            dfs(path+")", o, c+1)

        dfs("", 0, 0)
        return res